package org.example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test1 {
    //leetcode 56 合并区间 https://leetcode.cn/problems/merge-intervals/description/

    /**
     * 贪心
     * 先将intervals按照intervals[n][0]升序排序，如果intervals[n][0] == intervals[n+1][0]，
     * 那么就按照intervals[n][1]升序排序。排序完成之后，通过start和end记录处理重叠区间之后的开始和结束
     * 一直向后遍历更新start和end，当遇到没有重叠区间的时候，就将调整之后的start end区间添加到结果集中，
     * 并且更新start和end分别为intervals[i][0]和intervals[i][1]
     * 如果有重叠区间，也就是intervals[i][0]<=end，那么就更新end的值为end和intervals[i][1]的较大值
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            return a[0] - b[0];
        });
        int start = intervals[0][0], end = intervals[0][1], n = intervals.length;
        List<int[]> ret = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            if (intervals[i][0] > end) {
                ret.add(new int[]{start,end});
                start = intervals[i][0];
                end = intervals[i][1];
            }else {
                end = Math.max(end,intervals[i][1]);
            }
        }
        ret.add(new int[]{start,end});
        return ret.toArray(new int[][]{});
    }

    public static void main(String[] args) {
        Test1 test1 = new Test1();
        int[][] arr = new int[][]{{1,4},{4,5}};
        test1.merge(arr);
        System.out.println(666);
    }
}
